﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution40
{
    IList<IList<int>> res=new List<IList<int>>();
    public IList<IList<int>> CombinationSum2(int[] candidates, int target)
    {




        //DFS(candidates, target, startindex);
        IList<int> path=new List<int>();
        
        Array.Sort(candidates);
       
        
        
        DFS(candidates, target, 0, path);//起点不同
        return res;
    }

    //这个方法，结果数组有重复的原因是，candidates有重复的
    //解决想法，先去重，再使用这个方法
    //这个想法是错误的，因为结果 1，1，6是合法的

    private void DFS(int[] candidates, int target, int startindex, IList<int> path)
    {
        
        if (target < 0)
        {
            return;
        }
        if(target==0)
        {
            IList<int> newpath = new List<int>(path);
            res.Add(newpath);

        }
        if (startindex == candidates.Length)
        {
            return;
        }

        //每个数字两种选择，加入或者不加入

      

        for (int i = startindex; i < candidates.Length; i++) {
            //加入

            if (i> startindex && candidates[i] == candidates[i-1]) //重复,i>0防止越界,
                                                                   //这个地方，没有Used数组的原因是，第一个candidates[i-1]肯定会使用，后面的不使用
            {
                continue;
            }

            path.Add(candidates[i]);
            DFS(candidates, target - candidates[i], i + 1, path);
            path.RemoveAt(path.Count - 1);//回溯

        }




    }
    private void DFS2(int[] candidates, int target, int curindex, IList<int> path)
    {

        if (target < 0)
        {
            return;
        }
        if (target == 0)
        {
            IList<int> newpath = new List<int>(path);
            res.Add(newpath);

        }
        if (curindex == candidates.Length)
        {
            return;
        }

        //每个数字两种选择，加入或者不加入

        Console.WriteLine(curindex);
        //加入
        path.Add(candidates[curindex]);
        DFS2(candidates, target - candidates[curindex], curindex + 1, path);
        path.RemoveAt(path.Count - 1);//回溯

        //不加入
        DFS2(candidates, target, curindex + 1, path);



    }
}

class Program40
{

    static void Main40(string[] args)
    {
        Solution40 solution = new Solution40();
        int[] candidates = [10, 1, 2, 7, 6, 1, 5];
        int target = 8;
        
        IList<IList<int>> res = solution.CombinationSum2(candidates, target);
        for (int i = 0; i < res.Count; i++)
        {

            for (int j = 0; j < res[i].Count; j++)
            {
                Console.Write(res[i][j] + "  ");
            }
            Console.WriteLine();
        }
    }
}